The present invention relates to a device and method for grid routing and, more particularly, but not exclusively to grid routing on a segregated network.
U.S. patent application Ser. Nos. 11/615,977, 11/927,861 and 12/195,490 all assigned to ConteXtream, the contents of which are hereby incorporated by reference, teach a Grid Router as a distributed system consisting of three types of building blocks termed “Ingress Unit” (IU), “Egress Unit” (EU) and “Mailbox Unit” (MU) connected together via a transport network providing Clos like connectivity such that each IU is connected to each MU and each MU is connected to each EU. Clos-like networks are multi-stage switching networks. IU's and EU's are normally paired to form a single united “Ingress-Egress Unit” (IEU, also termed External Interface Unit—EIU), such that the above described topology can be described simply as a topology where each IEU is connected to each MU.
As described in the art, forwarding of traffic from IEU's to MU's is based on a hash function applied to packet headers and information derived from them resulting in the selection of a target MU normally selected uniformly among the set of MU's. Uniform selection assumes random packet headers or a wide variety of packet headers.
U.S. patent application Ser. No. 11/615,977, “Distributed Edge Network” by Barkai et al teaches, for each incoming data packet, each external interface unit may determine which mailbox unit may manage the mailbox for the service being transmitted by the data packet. Each external interface unit may perform a hashing function on at least some of the information in a header of the data packet. The resultant hash value may be the mailbox number within edge network for the service carried by the data packet. With the mailbox number, the external interface unit may directly write (typically using remote DMA (rDMA)) the data packet to the indicated mailbox.
The hashing functions performed by external interface units may be of any suitable sort, depending on the size of the network and the information available in the incoming data packets. In one embodiment, the hashing function may be a function of the source and/or destination addresses and a broadcast bit also found in the headers of data packets. In this embodiment, if the service is a point-to-multipoint service, as indicated by the broadcast bit, the mailbox for the service may be placed close to the source of the data and thus, the hashing may be performed on the source address. If the service is a multipoint-to-multipoint service, as indicated by the broadcast bit, the mailbox for the service may be placed anywhere and thus, the hashing may be performed on a combination of the source and destination addresses. If the service is a point-to-point service, the hashing may be performed on the source address or on the destination address, as desired. An exemplary hashing function may be “modulo 1000”.
In accordance with a preferred embodiment, administrative domains may be defined over the edge network of the present invention. Each domain may belong to a different vendor and may have its own table of services and its own hashing function but all the domains may utilize the same edge network. As described hereinabove, each domain allows plug and play access connections for devices and for data and media centers. Each device and/or center is added merely by adding the services they offer into the table of services. Moreover, each domain may route traffic anywhere in the metropolitan area, per subscriber per service.
U.S. patent application Ser. No. 11/927,861, “Grid Router” by Barkai et al. teaches that the hasher may review the headers stored in the storage area, taking each one in turn. The hasher may read each header, and may generate a hash value H.sub.1 from the data stored therein. The hash value H.sub.1 may indicate into which mailbox unit to transfer the packet. As discussed in U.S. patent application Ser. No. 11/615,977, the hash input may vary depending on the type of service carried by the packet. Typically, the packet may include an indication of the type of service carried therein.
In many networks, the connectivity between all IEU's and all MU's can be guaranteed, and the grid routers referred to above use uniform hashing functions which require such full connectivity. Grid routers with uniform hashing functions provide a scalable solution to network connectivity.
However, in a large class of networks, such as multi-service telecom access networks or cellular access networks the connectivity between these units is frequently more limited. In these cases, due to physical partitioning of the underlying transport network, an IEU may have connectivity to strictly defined subsets of MU's. We refer to such networks as segregated networks. The prior art grid routers cannot be used on such networks, which are left with non-scalable solutions.